package 每日一题;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class No16最接近的三数之和 {

    /**
     * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
     * 找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
     *
     * 示例：
     * 输入：nums = [-1,2,1,-4], target = 1
     * 输出：2
     * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
     */

    public static int threeSumClosest(int[] nums, int target) {

        Arrays.sort(nums);

        int result=Integer.MAX_VALUE;

        boolean flag=false;

        //两个指针都在i的右边会快
        for (int i = 0; i < nums.length-2; i++) {

            int left=i+1;
            int right=nums.length-1;

            while (left<right){

                int currentNum=nums[i];
                int leftNum=nums[left];
                int rightNum=nums[right];
                int sum=currentNum+leftNum+rightNum;//得出差
                /**
                 * cha为负数就会出问题
                 */
                int cha=sum-target;//和与目标数之差

                if(cha>0){
                    //大了,说明要right要往左移动
//                    result=Math.min(Math.abs(cha),result);
                    if(Math.abs(cha)<result) {
                        result = Math.abs(cha);
                        flag=false;
                    }
                    right--;
                }else if (cha<0){
                    //小于0了,说明left要往右移动
//                    result=Math.min(Math.abs(cha),result);
                    if(Math.abs(cha)<result) {
                        result = Math.abs(cha);
                        flag=true;
                    }
                    left++;
                }else{
                    //正好等于
                    return target;
                }

            }

        }

        return flag?target-result:target+result;

    }

    /**
     * 优化是在维护一个新abs(min),用min去比,而用result去接受三数之后,最后只用返回result即可
     */

    public static void main(String[] args) {//2(1) 16(4) 64(6)
//        System.out.println( "结果是:"+threeSumClosest(new int[]{-1,2,1,-4},1));
        System.out.println( "结果是:"+threeSumClosest(new int[]{0,0,0},1));
    }

}
